Problema computacional

Na ciência da teoria da computação, um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver. Por exemplo, o problema da fatoração

"Dado um inteiro positivo n, encontre um fator primo não-trivial de n."

é um problema computacional. Problemas computacionais são um dos principais objetos de estudo na ciência da teoria da computação. O campo de algoritmos estuda métodos de solução eficiente de problemas computacionais. O campo complementar de complexidade computacional tenta explicar porquê certos problemas computacionais são intratáveis por computadores.

Um problema computacional pode ser visto como uma coleção infinita de instâncias junto com uma solução para cada instância. Por exemplo, no problema da fatoração, as instâncias são os inteiros n, e as soluções são números primos p que descrevem fatores primos não-triviais de n.

É convencional representar ambas instâncias e soluções por strings binárias, a saber elementos de {0, 1}^*. Por exemplo, números podem ser representados como strings binárias usando-se codificação binária. (Para melhor leitura, identificamos números com suas codificações binárias nos exemplos abaixo.)